package com.wl2o2o.lanqiao.xzfourteen;

import java.util.Arrays;

/** 
* @author : WLei224
* @date ：2023年3月30日 上午11:10:17 
* 
*/
//归并排序
public class 快速排序{
  public static void main(String[] args){
      //二分思想：左右区间划分，递归
      int a[] = {49,38,65,97,76,13,27,49};
      quickSort1(a,0,a.length-1);
      System.out.println(Arrays.toString(a));
  }
  public static void quickSort1(int[] a, int left, int right){
      if(left > right) return ;
      //临时哨兵temp，作为基准点
      int i = left, j = right,temp = a[left];
      while(i != j){
          //从右往左
          while(a[j] >= temp && j > i) j--;
          if(j > i) a[i++] = a[j];
          while(a[i] <= temp && i < j) i++;
          if(i < j) a[j--] = a[i];
      } 

      a[i] = temp;
      quickSort1(a,left,i-1);
      quickSort1(a,i+1,right);
  }
//最终版本
	 public static void quickSort2(int[] a,int left,int right){
		 if(left>right) return;//区间擦肩而过，无效，不需要进行递归  
		 int i=left,j=right,temp = a[left];//a[left]作为基准点  
		 while(i!=j){
			while(a[j]>=a[temp] && j>i)
				   j--;//只要a[j]大于基准点继续往前移动j  if(j>i)
				   a[i++] = a[j];
			while(a[i]<=a[temp] && i<j)
				   i++;  
			if(i<j)a[j--] = a[i];
		 }
		 a[i] = temp;//基准点元素放到最终位置  quickSort(a,left,i-1);
		 quickSort2(a,i+1,right);
	 }
}